package AfterClass;

import java.util.Arrays;

public class homework1 {
	public static void main(String[] args) {
		int[] arr={5,3,7,2,9,8,1,4,6};
		quickSort(arr, 0, arr.length-1);
		System.out.println(Arrays.toString(arr));
		
		

}

	public static void quickSort(int[] arr, int l, int r){
		if(l>=r){
			return;
		}
		
		int x = arr[l+(int)(Math.random()*(r-l+1))];
		partition(arr, l, r, x);
		int left = first;
		int right = last;
		quickSort(arr, l, left-1);
		quickSort(arr, right+1, r);
	}
	
	public static int first, last;
	public static void partition(int[] arr, int l, int r, int x){
		first = l;
		last = r;
		int i = l;
		while(i<=last){
			if(arr[i] == x){
				i++;
			}
			else if(arr[i] < x){
				swap(arr, first++, i++);
			}
			else{
				swap(arr, last--, i);
			}
		}
	}
	
	
	public static void swap(int[] a, int i, int j){
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

}
